|
All networks, including biological networks, social networks, technological networks (e.g., computer networks and electrical circuits) and more, can be represented as graphs, which include a wide variety of subgraphs. One important local property of networks are so-called network motifs, which are defined as recurrent and statistically significant sub-graphs or patterns. Network motifs are sub-graphs that repeat themselves in a specific network or even among various networks. Each of these sub-graphs, defined by a particular pattern of interactions between vertices, may reflect a framework in which particular functions are achieved efficiently. Indeed, motifs are of notable importance largely because they may reflect functional properties. They have recently gathered much attention as a useful concept to uncover structural design principles of complex networks. Although network motifs may provide a deep insight into the network’s functional abilities, their detection is computationally challenging. ==Definition== Let and be two graphs. Graph is a ''sub-graph'' of graph (written as ) if and . If and contains all of the edges with , then is an ''induced sub-graph'' of . We call and isomorphic (written as ), if there exists a bijection (one-to-one) with for all . The mapping is called an isomorphism between and . When and there exist an isomorphism between the sub-graph and a graph , this mapping represents an ''appearance'' of in . The number of appearances of graph in is called the frequency of in . A graph is called ''recurrent'' (or ''frequent'') in , when its ''frequency'' is above a predefined threshold or cut-off value. We used terms ''pattern'' and ''frequent sub-graph'' in this review interchangeably. There is an ensemble of random graphs corresponding to the null-model associated to . We should choose random graphs uniformly from and calculate the frequency for a particular frequent sub-graph in . If the frequency of in is higher than its arithmetic mean frequency in random graphs , where , we call this recurrent pattern ''significant'' and hence treat as a ''network motif'' for . For a small graph , the network and a set of randomized networks , where , the ''Z-Score'' that has been defined by the following formula: where and stand for mean and standard deviation frequency in set , respectively. The larger the , the more significant is the sub-graph as a motif. Alternatively, another measurement in statistical hypothesis testing that can be considered in motif detection is the P-Value, given as the probability of (as its null-hypothesis), where indicates the frequency of G' in a randomized network.〔 A sub-graph with P-value less than a threshold (commonly 0.01 or 0.05) will be treated as a significant pattern. The P-value is defined as Where indicates number of randomized networks, is defined over an ensemble of randomized networks and the Kronecker delta function is one if the condition holds. The concentration of a particular n-size sub-graph in network refers to the ratio of the sub-graph appearance in the network to the total ''n''-size non-isomorphic sub-graphs’ frequencies, which is formulated by where index is defined over the set of all non-isomorphic n-size graphs. Another statistical measurement is defined for evaluating network motifs, but it is rarely used in known algorithms. This measurement is introduced by Picard ''et al.'' in 2008 and used the Poisson distribution, rather than the Gaussian normal distribution that is implicitly being used above. In addition, three specific concepts of sub-graph frequency have been proposed. As figure illustrates, the first frequency concept considers all matches of a graph in original network. This definition is similar to what we have introduced above. The second concept is defined as the maximum number of edge-disjoint instances of a given graph in original network. And finally, the frequency concept entails matches with disjoint edges and nodes. Therefore, the two concepts and restrict the usage of elements of the graph, and as can be inferred, the frequency of a sub-graph declines by imposing restrictions on network element usage. As a result, a network motif detection algorithm would pass over more candidate sub-graphs if we insist on frequency concepts and . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「network motif」の詳細全文を読む スポンサード リンク
|